package com.leet.bfs;

import java.util.*;

public class TheLeastPriceFlight {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // 返回的结果
        int ans = Integer.MAX_VALUE;
        // 首先创建map（segment),存放数据
        Map<Integer, List<int[]>> sgm = new HashMap<>();
        // 遍历flights信息，放到segment里去
        for(int[] flight: flights){
            // new 的 ArrayList与List<int[]>对应，得不到就创建
            List<int[]> flightTo = sgm.getOrDefault(flight[0], new ArrayList<>());
            // 在目标对象中放入目标对象的坐标和从a-b的价值
            flightTo.add(new int[]{flight[1],flight[2]});
            // 存入map中
            sgm.put(flight[0],flightTo);
        }
        // 存放到达该节点的最小值价值的数组, 初始化初值
        int[] minValues = new int[n];
        Arrays.fill(minValues,Integer.MAX_VALUE);
        // 开始的src总价值为0
        minValues[src] = 0;

        // 存放当前位置的queue和当前价值的queue
        Queue<Integer> qPos = new LinkedList<>();
        Queue<Integer> qVal = new LinkedList<>();
        //初始化当前位置和当前的变量
        qPos.offer(src);
        qVal.offer(0);
        // 记录k的值，如果比k大，那么break
        int count = 0;
        while(!qPos.isEmpty()){
            // 已经超时
            if(count > k) break;
            int size = qPos.size();
            for(int i = 0 ;i < size; i++){
                // 找到头，然后遍历头
                Integer posHead = qPos.poll();
                // 到目前为止的总value
                Integer valHead = qVal.poll();
                // 遍历头
                for(int[] nextFlight:sgm.getOrDefault(posHead,new ArrayList<>())){
                    if(nextFlight[0] == dst){
                        ans = Math.min(ans,valHead+nextFlight[1]);
                        continue;
                    }
                    // 和之前的到达下一站的minValue比较如果小，才继续走
                    if(valHead+nextFlight[1] < minValues[nextFlight[0]]){
                        // 更新
                        minValues[nextFlight[0]] = valHead+nextFlight[1];
                        qPos.offer(nextFlight[0]);
                        qVal.offer(valHead+nextFlight[1]);
                    }
                }

            }
            count++;
        }

        if(ans == Integer.MAX_VALUE) return -1;

        return ans;
    }



}
